package algorithm.swordoff;

/**
 * 树的子结构
 */

public class SQ26 {

    /**
     * B是否为A的子结构
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return A != null && B != null && (recursion(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    /**
     * 从两个根节点A和B遍历判断B是否为A的子树
     * @param A
     * @param B
     * @return
     */
    public boolean recursion(TreeNode A, TreeNode B) {
        // 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true
        if (B == null) return true;
        // 当节点 A 为空(隐含条件是B还不空)：说明已经越过树 A 叶子节点，即匹配失败，返回 false
        else if (A == null) return false;
        // 当节点 A 和 B 的值不同：说明匹配失败，返回 false
        else if (A.val != B.val) return false;
        else return recursion(A.left, B.left) && recursion(A.right, B.right);
    }

}
